//
// Created by haoly on 2025/5/15.
//
#include <stdio.h>
#include <stdlib.h>

#include "PQ.h"

static int N;
Item *pq;


void fixUp(Item a[], int k){
    while (k > 1 && less(a[k/2], a[k])) {
        exch(a[k/2], a[k]);
        k = k/2;
    }
}

void fixDown(Item a[], int k, int N) {
    int j;
    while (2*k <= N) {
        j = 2 * k;
        if (j < N && less(a[j], a[j+1])) {
            j++;
        }
        if (!less(a[k], a[j])) {
            break;
        }
        exch(a[k], a[j]);
        k = j;
    }
}


void PQinit(int maxN) {
    pq = malloc((maxN+1) * sizeof(Item));
    N = 0;
}
int PQempty() {
    return N == 0;
}
void PQinsert(Item v) {
    pq[++N] = v;
    fixUp(pq, N);
}
Item PQdelmax() {
    exch(pq[1], pq[N]);
    fixDown(pq, 1, N-1);
    return pq[N--];
}

void printPQ() {
    int i;
    for (i = 1; i <=N; i++) {
        printf("%c ", pq[i]);
    }
    printf("\n");
}